// 思路：先malloc出一大块内存，之后每次申请都在这个内存块里拿空间
// 1.New 从内存块里拿取
//  每次New一个新空间时，都先从被删除的内存小块里拿取
// 2.Delete 每个删除的内存小块，里面都要存放一个指针(头4/8个字节存储)，用于指向下一个被删除的内存小块(链表)

#include <iostream>
#include <vector>
#include <time.h>
using std::cout;
using std::endl;

template <class T>
class Memorypool
{
public:
    void TestObjectPool()
    {
        // 申请释放的轮次
        const size_t Rounds = 5;

        // 每轮申请释放多少次
        const size_t N = 10000000;

        std::vector<int *> v1;
        v1.reserve(N);

        size_t begin1 = clock();
        for (size_t j = 0; j < Rounds; ++j)
        {
            for (int i = 0; i < N; ++i)
            {
                v1.push_back(new int);
            }
            for (int i = 0; i < N; ++i)
            {
                delete v1[i];
            }
            v1.clear();
        }

        size_t end1 = clock();

        std::vector<int *> v2;
        v2.reserve(N);

        Memorypool<int> TNPool;
        size_t begin2 = clock();
        for (size_t j = 0; j < Rounds; ++j)
        {
            for (int i = 0; i < N; ++i)
            {
                v2.push_back(TNPool.New());
            }
            for (int i = 0; i < N; ++i)
            {
                TNPool.Delete(v2[i]);
            }
            v2.clear();
        }
        size_t end2 = clock();

        cout << "new cost time:" << end1 - begin1 << endl;
        cout << "object pool cost time:" << end2 - begin2 << endl;
    }
    T *New()
    {
        // 先从删除链表中取内存块
        if (_deletelist)
        {
            // 采用头删
            void *next;                     // 头节点的下一个位置
            next = *((void **)_deletelist); // 对deletelist(第一个节点)的头4/8个字节进行解引用，里面存储的是头节点下一个节点的指针
            T *start = (T *)_deletelist;
            _deletelist = next;
            return start;
        }

        size_t pointerlen = sizeof(*(void **)_deletelist);
        // 如果大内存块为空或者剩余内存不足,要重新申请一次
        if (_rememory < sizeof(T))
        {
            _rememory = 1024 * 1024;              // 更新内存块的大小
            _memory = (char *)malloc(_rememory); //_memory指向新申请来的大内存块
            if(_memory < 0)
            {
                throw std::bad_alloc();
                exit(1);
            }
        }

        T *start = (T*)_memory; // start指向当前大内存块的初始位置

        // ①如果申请的内存比指针小，那么归还内存时无法存储下一个被删除内存的指针，需要固定给一个指针大小的内存给用户
        // ②如果申请的内存大于等于指针的大小，那么就直接给(暂时不考虑申请内存过大问题)
        size_t size = sizeof(T) < pointerlen ? pointerlen : sizeof(T); //*(void**)的结果是void*的本身，即该机器下指针的内容，再用sizeof计算出指针的大小
        _rememory -= size;
        _memory += size; // char*的加减操作都是1Byte

        // 申请出内存后，需要对内存进行初始化(定位new)
        new (start) T;

        return start;
    }
    void Delete(T *obj)
    {
        // 先将内存块的内容进行初始化
        obj->~T();
        // 删除链表进行头插
        *((void **)obj) = _deletelist; // 先让被删除的内存块指向头节点,用内存块的前4/8个字节做存储
        _deletelist = obj;
    }

private:
    char *_memory = nullptr;     // 用来指向大块内存块里初始位置的指针(多次申请后，每次都要更新_memory的位置)
    size_t _rememory = 0;        // 剩余内存块的大小
    void *_deletelist = nullptr; // 用户删除的内存块中,删除链表的第一个节点地址
};